class Solution:
    def countPrimes(self, n: int) -> int:

        if n<3:
            return 0

        cnt = [1] * n
        cnt[0], cnt[1] = 0, 0

        for i in range(2, n, 1):
            if cnt[i] == 1:
                x = 2
                while x*i < n:
                    cnt[int(x*i)] = 0
                    x+=1

        return sum(cnt) 


